package example.字符串.对称补齐;

import java.util.Stack;

/**
 * 成对的69匹配序列定义为：
 * <p>
 * 1、 空串""是一个成对的69序列；
 * 2、如果"X"和"Y"是成对的69序列，那么"XY"也是成对的69序列；
 * 3、如果"X"是一个成对的69序列，那么"6X9"也是一个成对的69序列；
 * 4、每个成对的69序列都可以由以上规则生成。 例如，"", "69", "6699", "6969"都是成对的。
 * 现在给出一个序列S，允许你的操作是： 在S的开始和结尾出添加一定数量的6或者9，
 * 使序列S变为一个成对的69序列。输出添加最少的6或者9之后成对的69序列是什么。
 */
public class Demo2 {

    /**
     * 与生成有效括号的方式相同，不断平衡成对的69，缺6往前补6，缺9往后补9
     *
     * @param S
     * @return
     */
    public static String Paired69(String S) {
        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for (char c : S.toCharArray()) {
            if (c == '6') {
                stack.push(c);
            } else {
                //有一个就9就弹出一个6，否则前面补6
                if (!stack.isEmpty())
                    stack.pop();              // 还有6就弹出来与9配对
                else
                    sb.insert(0, '6');     // 否则缺6，需要在前面补
            }
            sb.append(c);
        }
        while (!stack.isEmpty()) {       // 6有余，往后补9
            stack.pop();
            sb.append('9');
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(Paired69("96"));
    }
}
